package list;

public class LinkedListCreate {

	// 单向链表
	public static ListNode createList(int[] array) {
		if (array == null || array.length == 0) {
			return null;
		}
		ListNode headNode = new ListNode(array[0]);
		ListNode temp = headNode;
		for (int i = 1; i < array.length; i++) {
			temp.next = new ListNode(array[i]);
			temp = temp.next;
		}
		return headNode;
	}

	// 添加结点
	public static void addNode(ListNode head, int value) {
		ListNode node = new ListNode(value);
		node.next = null;
		// 如果头结点为空
		if (head == null) {
			head = node;
		} else {
			ListNode temp = head;
			while (temp.next != null) {
				temp = temp.next;
			}
			temp.next = node;
		}
	}

	// 插入节点,插入的节点位于InsertPosi后面
	public static void insertListNode(ListNode head, int insertPosi, int value) {
		ListNode tempNode = head;
		for (int i = 0; i < insertPosi; ++i) {
			tempNode = tempNode.next;
			if (tempNode == null) {
				System.err.println("您输入的节点位置超过链表长度");
				return;
			}
		}
		ListNode node = new ListNode(value);
		node.next = tempNode.next;
		tempNode.next = node;

	}

	public static void deleteListNode(ListNode head, int delPosition) {
		ListNode tempNode = head;
		ListNode preListNode = null; // 前件结点
		int count = 0;
		while (tempNode != null) {
			if (count == delPosition) {
				// 如果要删除的是头结点
				if (tempNode == head) {
					head = tempNode.next;
					// 将原来的头结点置空
					tempNode = null;
				} else {
					preListNode.next = tempNode.next;
					tempNode = null;
				}
				return;
			}
			preListNode = tempNode; // 前件结点始终在tempListNode之前
			tempNode = tempNode.next;
			count++;
		}
		System.err.println("未找到该结点");
	}

	public static void printList(ListNode node) {
	    if(hasLoop(node)){
            System.err.println("the list has loop, please check");
            return;
        }
		while (node != null) {
			System.out.print(node.val + "  ");
			node = node.next;
		}
		System.out.println();
	}

	public static void main(String[] args) {

		int[] a1 = { 5, 6, 9, 45, 61, 70, 75, 89 };
		int[] a2 = { 2, 4, 11, 26, 68 };
		// 头结点
		ListNode head1 = createList(a1);
		ListNode head2 = createList(a2);
		// 对两个链表合并，两个链表都是排好序
		// 输出排序的链表
		// can accept null input
		ListNode mergeListNode = merge(head1, head2);
		while (mergeListNode != null) {
			System.out.print(mergeListNode.val + "  ");
			mergeListNode = mergeListNode.next;
		}
		System.out.println("-----");
		insertListNode(head1,0,56);
		printList(head1);
		deleteListNode(head1, 0);
		System.out.println();
		printList(head2);
		System.out.println();
	}

	public static ListNode merge(ListNode head1, ListNode head2) {
		// 如果两者中有一个为空，那么返回另外一个。两个为空，返回null
		if (head1 == null) {
			return head2;
		} else if (head2 == null) {
			return head1;
		}
		ListNode pmergeHead = null;
		// 将两者中小的设为新的结点
		if (head1.val < head2.val) {
			pmergeHead = new ListNode(head1.val);
			// 递归调用，将head1设为新的头结点，head2不变
			pmergeHead.next = merge(head1.next, head2);
		} else {
			pmergeHead = new ListNode(head2.val);
			pmergeHead.next = merge(head1, head2.next);
		}
		// 返回新的链表头结点
		return pmergeHead;
	}
	
	public static int getLength(ListNode list){
		int res = 0;
		while(list != null){
			res++;
			list = list.next;
		}
		return res;
	}

	public static boolean hasLoop(ListNode head){
		ListNode quick = head;
		ListNode slow = head;

		while(quick != null && quick.next != null){
		    quick = quick.next.next;
		    slow = slow.next;
		    if(quick == slow){
		        return true;
            }
        }
        return false;
	}
}
